// Package tree
/*

方法1：
时间复杂度：O()
空间复杂度：O()

case1:

r:

*/
package tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/*
时间复杂度:O(n^2) 对于每个节点，都需要遍历一遍以该节为根节点的所有子孙节点，就是说对于第一个节点需要遍历n次，第二个节点需要遍历n-1次
空间复杂度:O(n) 总共n个节点，递归调用栈n层
*/
func pathSum(root *TreeNode, targetSum int) int {
	if root == nil {
		return 0
	}
	// 总路径数=路径中包含root的路径树+左子树的总路径树+右子树的总路径树
	return helper2(root, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}

// 计算路径中包含root节点的路径数
func helper2(root *TreeNode, targetSum int) int {
	if root == nil {
		return 0
	}
	res := 0
	if root.Val == targetSum {
		res++
	}
	return res + helper2(root.Left, targetSum-root.Val) + helper2(root.Right, targetSum-root.Val)
}

/*
时间复杂度:O(N) dfs每次遍历一个节点，一共有n个节点
空间复杂度:O(N) 递归调用栈
*/
func pathSum2(root *TreeNode, targetSum int) int {
	preSum := map[int64]int{
		0: 1,
	}
	var ans int
	// 这里用int64是因为要进行多个数值的相加，可能会超出int范围
	var dfs func(node *TreeNode, cur int64)
	dfs = func(node *TreeNode, cur int64) {
		if node == nil {
			return
		}
		cur += int64(node.Val)
		ans += preSum[cur-int64(targetSum)]
		preSum[cur]++
		dfs(node.Left, cur)
		dfs(node.Right, cur)
		// 深度优先，退出当前节点x返回上一节点y时，由targetSum表示以当前遍历到的节点为末尾节点的序列，所以返回到上一节点y之后，
		// targetSum的末尾节点就变成了y，而preSum[cur]--就是去除了已退出节点x的影响
		preSum[cur]--
	}
	dfs(root, 0)
	return ans
}
